home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / grabst / relay.c < prev    next >
C/C++ Source or Header  |  1990-03-06  |  10KB  |  437 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /* relay.c - routines to re-layout a graph */
  9.  
  10. #include "malloc.h"
  11. #include "attribute.h"
  12. #include "digraph.h"
  13. #include "debug.h"
  14.  
  15. OUTEDGE *get_edge();
  16. INEDGE *get_in_edge();
  17.  
  18. relay_digraph(digraph)
  19. register DIGRAPH *digraph;
  20. {
  21.       /* reset the node's widths */
  22.     reset_node_width(digraph);
  23.  
  24.       /* reset ordinalities and directions of edges */
  25.     reset_edge_ord(digraph);
  26.  
  27.       /* trash the dummy nodes */
  28.     trash_dummy_nodes(digraph);
  29.  
  30.       /* compact the nodes array, i.e. digraph->nodes[] */
  31.     compact_nodes_array(digraph);
  32.  
  33.       /* update the vno in the edge lists after compaction */
  34.     update_edge_lists_vno(digraph);
  35.  
  36.       /* reset the node fields which need resetting */
  37.     reset_nodes(digraph);
  38.  
  39.       /* fix ante and succ sets of the nodes */
  40.     fix_ante_succ_sets(digraph);
  41.  
  42.       /* resets fields in digraph */
  43.     reset_digraph(digraph);
  44.  
  45.     make_proper(digraph);
  46.     minimize_crossings(digraph);
  47.     layout_levels(digraph);
  48. }
  49.  
  50. trash_dummy_nodes(digraph)
  51. register DIGRAPH *digraph;
  52.   /* remove the dummy nodes */
  53. {
  54.     VNO vno;
  55.     register NODE *node;
  56.  
  57.     all_nodes(digraph, node)
  58.     loop
  59.     if (Is_dummy(node)) 
  60.     {
  61.         vno = Vno(node);
  62.         dispose(Ante_set(node));
  63.         dispose(Succ_set(node));
  64.         dispose(Text(node));
  65.  
  66.         dispose_vertex(digraph, Name(node));
  67.         dispose(node);
  68.         Node(digraph, vno) = NULL;
  69.     }
  70.     endloop
  71. }
  72.  
  73. static VNO vno_map[MAXNODES];    /* holds new vno values for the nodes */
  74. #define NO_CHANGE    -1
  75.  
  76. compact_nodes_array(digraph)
  77. register DIGRAPH *digraph;
  78.   /* squish the nodes array so the only empty spots are at the end */
  79. {
  80.     register int i, j;
  81.  
  82.     for (i = 0; i < MAXNODES; i++) 
  83.     {
  84.     vno_map[i] = NO_CHANGE;
  85.     }
  86.  
  87.     for (i = 0, j = 0; i < MAXNODES; i++) 
  88.     {
  89.     if (digraph->nodes[i] == NULL)
  90.     {
  91.         continue;
  92.     }
  93.     else if (i == j)
  94.     {
  95.         j++;
  96.         continue;
  97.     }
  98.     else
  99.     {
  100.         digraph->nodes[i]->vertex->vno = j;
  101.         vno_map[i] = j;
  102.         digraph->nodes[j] = digraph->nodes[i];
  103.         digraph->nodes[i] = NULL;
  104.         j++;
  105.     }
  106.     }
  107.  
  108.     digraph->lastnode = j - 1;
  109. }
  110.  
  111. update_edge_lists_vno(digraph)
  112. DIGRAPH *digraph;
  113.   /**
  114.      update various vno values using vno_map:
  115.     coalescer_vno for coalesced nodes
  116.     expansion sets for coalescer nodes
  117.     from_vno and to_vno fields of in- and out- edges.
  118.    **/
  119. {
  120.     register NODE *node;
  121.     register VNO old_to_vno;
  122.     register VNO old_from_vno;
  123.     register VNO old_coalescer_vno;
  124.     register VNO old_exp_vno;
  125.     register INEDGE *in_edge;
  126.     register OUTEDGE *out_edge;
  127.     SET *old_exp_set;
  128.  
  129.     all_nodes(digraph, node)
  130.     loop
  131.     if (Coalesced(node))
  132.     {
  133.         old_coalescer_vno = Coalescer_vno(node);
  134.  
  135.         if (vno_map[old_coalescer_vno] != NO_CHANGE)
  136.         {
  137.         Coalescer_vno(node) = vno_map[old_coalescer_vno];
  138.         }
  139.     }
  140.  
  141.     if (Coalescer(node))
  142.     {
  143.         old_exp_set = Expansion(node);
  144.         init_set(Expansion(node));
  145.  
  146.         each_element(old_exp_set, old_exp_vno)
  147.         loop
  148.             if (vno_map[old_exp_vno] != NO_CHANGE)
  149.             {
  150.                   add_element(Expansion(node), vno_map[old_exp_vno]);
  151.             }
  152.         else
  153.         {
  154.             add_element(Expansion(node), old_exp_vno);
  155.         }
  156.         endloop;
  157.  
  158.         dispose(old_exp_set);
  159.     }
  160.  
  161.     all_in_edges(node, in_edge)
  162.     loop
  163.         old_from_vno = in_edge->from_vno;
  164.  
  165.         if (vno_map[old_from_vno] != NO_CHANGE) 
  166.         {
  167.         in_edge->from_vno = vno_map[old_from_vno];
  168.         }
  169.     endloop
  170.  
  171.     all_out_edges(node, out_edge)
  172.     loop
  173.         old_to_vno = out_edge->to_vno;
  174.  
  175.         if (vno_map[old_to_vno] != NO_CHANGE) 
  176.         {
  177.         out_edge->to_vno = vno_map[old_to_vno];
  178.         }
  179.     endloop
  180.     endloop
  181. }
  182.  
  183. reset_edge_ord(digraph)
  184. DIGRAPH *digraph;
  185.   /**
  186.      unreverse reversed edges and reset the ordinality of edges.
  187.      Unreversing the edges helps put the graph back in a state similar
  188.      to when it was read in, which allows the layout routines to layout
  189.      the graph in the same way.
  190.    **/
  191. {
  192.     NODE *node, *next_node;
  193.     OUTEDGE *outedge;
  194.     INEDGE *inedge;
  195.     int max, i, j;
  196.     SET *visited;
  197.  
  198.     all_nodes(digraph, node)
  199.     loop
  200.     if (Is_dummy(node))
  201.     {
  202.         continue;
  203.     }
  204.     
  205.     all_out_edges(node, outedge)
  206.     loop
  207.         if (Edge_reversed(outedge))
  208.         {
  209.             reverse_edge(digraph, Vno(node), To_vno(outedge), Ord(outedge));
  210.         }
  211.     endloop;
  212.     endloop;
  213.  
  214.     init_set(visited);
  215.  
  216.     all_nodes(digraph, node)
  217.     loop
  218.     clear_set(visited);
  219.  
  220.       /**
  221.          update the ordinalities using all out edges, which could contain
  222.          some repeats.  Visited is used to skip repeats.  It would be
  223.          nicer to use Succ_set, but that could be (probably is) messed
  224.          up and won't be fixed until later
  225.        **/
  226.     all_out_edges(node, outedge)
  227.     loop
  228.         if (!in(visited, To_vno(outedge)))
  229.         {
  230.         add_element(visited, To_vno(outedge));
  231.             next_node = Node(digraph, To_vno(outedge));
  232.             max = max_edges(node, next_node);
  233.             j = 1;
  234.  
  235.             for (i = 1; i <= max; i++)
  236.             {
  237.             if ((outedge = get_edge(digraph, node, next_node, i)) 
  238.                != NULL)
  239.             {
  240.                 inedge = get_in_edge(digraph, node, next_node, i);
  241.                 Ord(outedge) = j;
  242.                 Ord(inedge) = j;
  243.                 j++;
  244.             }
  245.         }
  246.         }
  247.     endloop;
  248.     endloop;
  249.  
  250.     dispose(visited);
  251. }
  252.  
  253. reset_nodes(digraph)
  254. DIGRAPH *digraph;
  255.   /* reset node fields that need resetting */
  256. {
  257.     register int i;
  258.     register NODE *node;
  259.  
  260.     for (i = 0; i <= digraph->lastnode; i++) 
  261.     {
  262.     node = digraph->nodes[i];
  263.  
  264.     dispose(Ante_set(node));
  265.     dispose(Succ_set(node));
  266.  
  267.     init_set(Succ_set(node));
  268.     init_set(Ante_set(node));
  269.     init_member(Node_member(node));
  270.  
  271.     Status(node) = NORMAL;        /* dummy nodes are all gone */
  272.     Y_position(node) = X_position(node) = 0;
  273.     Is_layed(node) = FALSE;
  274.  
  275.     /* halfheight and halfwidth fields already taken care of */
  276.     }
  277. }
  278.  
  279. reset_node_width(digraph)
  280. DIGRAPH *digraph;
  281.   /* change the node width, just in case edges have been added/deleted */
  282. {
  283.     NODE *node, *node2;
  284.     VNO vno;
  285.     int max;
  286.  
  287.     all_nodes(digraph, node)
  288.     loop
  289.     if (Is_dummy(node))
  290.       /* dummy nodes are trashed on the next step, so just skip them */
  291.     {
  292.         continue;
  293.     }
  294.  
  295.     max = 0;
  296.  
  297.     each_element(Ante_set(node), vno)
  298.     loop
  299.         node2 = Node(digraph, vno);
  300.         max = MAX(num_edges(node2, node), max);
  301.     endloop;
  302.  
  303.     each_element(Succ_set(node), vno)
  304.     loop
  305.         node2 = Node(digraph, vno);
  306.         max = MAX(num_edges(node, node2), max);
  307.     endloop;
  308.  
  309.         switch (Shape(node))
  310.         {
  311.             case POINT:
  312.                 Half_width(node) = DUMMY_HALF_WIDTH;
  313.             break;
  314.             case DIAMOND:
  315.                 Half_width(node) = Node_half_width(node) + HALF_CHAR * 2;
  316.           /* 2 extra chars to avoid pinching chars at the end */
  317.             break;
  318.             case CIRCLE:
  319.                 Half_width(node) = Node_half_width(node);
  320.             break;
  321.             case OVAL:
  322.                 Half_width(node) = Node_half_width(node);
  323.             break;
  324.             case DOUBLE_BOX:
  325.             case RECTANGLE:
  326.                 Half_width(node) = Node_half_width(node);
  327.             break;
  328.             default:
  329.             PrintError("reset_nodes:  illegal shape");
  330.             break;
  331.         }
  332.  
  333.     fix_width(node, max);
  334.     endloop;
  335. }
  336.  
  337. fix_ante_succ_sets(digraph)
  338. register DIGRAPH *digraph;
  339.   /**
  340.      use the outedges to properly set the antecedent and succedent sets.
  341.      must insure:  Displayed edges are in the ante/succ sets.
  342.            Coalesced nodes have the proper ante and succ sets (but
  343.              no displayed node has a coalesced node in its ante or
  344.              succ sets).  If coalesced nodes don't have the proper
  345.              antecedent and successor sets, expanding a node could
  346.              be tricky.
  347.            A node is not in its own ante/succ set.
  348.  
  349.      Note that non-displayed nodes (coalesced and hidden nodes) may contain
  350.      hidden nodes in their ante/succ sets.  As long as this routine is called
  351.      after every display/hide/coalesce/expand, this is fine.
  352.    **/
  353. {
  354.     register NODE *node;
  355.     register OUTEDGE *out_edge;
  356.     VNO fromvno, tovno;
  357.  
  358.     all_nodes(digraph, node)
  359.     loop
  360.     if (Coalescer(node) || Is_dummy(node))
  361.       /* we only care about nodes with outedges */
  362.     {
  363.         continue;
  364.     }
  365.  
  366.     fromvno = Vno(node);
  367.  
  368.     while (Coalesced(Node(digraph, fromvno)))
  369.       /* get the coalescer node which contains this one */
  370.     {
  371.         fromvno = Coalescer_vno(Node(digraph, fromvno));
  372.     }
  373.  
  374.     all_out_edges(node, out_edge)
  375.     loop
  376.         tovno = To_vno(out_edge);
  377.  
  378.           /**
  379.          Get the coalescer node which contains this one. 
  380.          Along the way, put fromvno in the ancestor sets of the
  381.          nodes
  382.            **/
  383.         while (Coalesced(Node(digraph, tovno)))
  384.         {
  385.         if (fromvno != tovno)
  386.         {
  387.                 add_element(Node(digraph, tovno)->ante_set, fromvno);
  388.         }
  389.  
  390.             tovno = Coalescer_vno(Node(digraph, tovno));
  391.         }
  392.  
  393.           /**
  394.          We've already got the proper value for fromvno, but
  395.          we also need to put tovno in the successor sets for
  396.          those nodes, so...
  397.            **/
  398.         fromvno = Vno(node);
  399.  
  400.         while (Coalesced(Node(digraph, fromvno)))
  401.         {
  402.         if (fromvno != tovno)
  403.         {
  404.             add_element(Node(digraph, fromvno)->succ_set, tovno);
  405.         }
  406.  
  407.             fromvno = Coalescer_vno(Node(digraph, fromvno));
  408.         }
  409.  
  410.           /* add the link for displayed nodes */
  411.         if (Displayed(Node(digraph, tovno)) && 
  412.         Displayed(Node(digraph, fromvno)) && fromvno != tovno)
  413.         {
  414.             add_element((Node(digraph, fromvno))->succ_set, tovno);
  415.             add_element((Node(digraph, tovno))->ante_set, fromvno);
  416.         }
  417.     endloop;
  418.     endloop;
  419. }
  420.  
  421. reset_digraph(digraph)
  422. register DIGRAPH *digraph;
  423. {
  424.     LEVEL *level;
  425.  
  426.       /* first, free levels structure */
  427.     each_level(digraph, level)
  428.     loop
  429.     dispose(Members(level));
  430.     dispose(level);
  431.     endloop;
  432.  
  433.       /* now reset some of the fields */
  434.     digraph->levels = NULL;
  435.     digraph->lastlevel = NULL;
  436. }
  437.